home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 August: Tool Chest / Dev.CD Aug 94.toast / New System Software Extensions / Thread Manager Extension 2.0.1 / Sample Applications / Power Examples / SortPicts / Source / HeapSort.cp < prev    next >
Encoding:
Text File  |  1994-06-03  |  2.6 KB  |  124 lines  |  [TEXT/MPS ]
  1. /*************************************************************************************
  2.  *
  3.  *    Apply a Heap Sort Algorithm to an offscreen, scrambled GWorld
  4.  *
  5.  *    HeapSort.cp    -    C Source
  6.  *
  7.  *      Copyright © Apple Computer, Inc. 1988 - 1993
  8.  *      All rights reserved.
  9.  *
  10.  *    This is the "meat" of the SortPicts program.  This file supplies the
  11.  *      core functionality to SortPicts by overiding and supplementing
  12.  *      the WindowObj class.  
  13.  *
  14.  *************************************************************************************/
  15. #include "GWorldObj.h"
  16.  
  17. /*************************************************************/
  18. /*                                                           */
  19. /*               The Actual Sort Algorithms                  */
  20. /*                                                           */
  21. /*************************************************************/
  22.  
  23.  
  24.  
  25. void    GWorldObj::HeapSort( void)
  26. {
  27.     
  28.     long            loop;
  29.     long            size;
  30.     long            *tickPtr = (long *)0x16A;
  31.     char            mmuMode = true32b;
  32.     
  33.     UseGWorld();
  34.  
  35.     SetTitle( (const unsigned char*)"\pHeap Sorting");
  36.  
  37. #ifdef DEMO
  38.     //    This offsets for drawing directly to the screen
  39.     offscreenPtr -= (long) ((**(((CWindowPtr)me)->portPixMap)).bounds.top * pictRowBytes) +
  40.                     (**(((CWindowPtr)me)->portPixMap)).bounds.left;
  41. #endif
  42.     
  43.     HLock( (Handle)sortList);
  44.     sortListPtr = *sortList;
  45.     if( !sortListPtr)
  46.         return;
  47.  
  48.     BuildHeap();
  49.  
  50.     SwapMMUMode( &mmuMode);
  51.     
  52.     size = N - 1;
  53.     for( loop = N-1; loop; --loop)
  54.     {
  55.         if( YieldIfTime( &mmuMode))
  56.             goto SortErrQuit;
  57.             
  58.         ExchangeSortItem( 0, loop);
  59.         
  60.         Heapify( --size, 0);
  61.     }        
  62.     
  63.  
  64.     UnuseGWorld();
  65.     SwapMMUMode( &mmuMode);
  66.  
  67. SortErrQuit:
  68.     HUnlock( (Handle)sortList);
  69.     SetTitle( (const unsigned char*)"\pDone");
  70.     
  71.     doneSorting = true;
  72.     finishedTime = TickCount();
  73.     DrawObj();
  74. }
  75.  
  76. void    GWorldObj :: BuildHeap( void)
  77. {
  78.     long        loop;
  79.  
  80.     for( loop = (N>>1)+3; loop; --loop)
  81.         Heapify( N-1, loop -1);
  82.  
  83. }
  84.  
  85. //
  86. //        This code adjusts for a zerø based array
  87. //        (Where as the original source from Sedgewick (good book)
  88. //        was 1..N, not 0..N-1
  89. //
  90.  
  91. #define        Left(i)            (((i+1) << 1) -2)
  92. #define        Right(i)        (((i+1) << 1) -1)
  93.  
  94. //
  95. //    Typically, I would have used
  96. //    #define        Left(i)            ((i) << 1)
  97. //    #define        Right(i)        (((i) << 1) + 1)
  98. //    #endif
  99.  
  100. void    GWorldObj :: Heapify( long size, long index)
  101. {
  102.     long    left, right, largest;
  103.     
  104.     left = Left( index);
  105.     right = Right( index);
  106.     
  107.     largest = index;
  108.     
  109.     if( left <= size)
  110.         if( sortListPtr[left] > sortListPtr[index])
  111.             largest = left;
  112.     
  113.     if( right <= size)
  114.         if( sortListPtr[right] > sortListPtr[largest])
  115.             largest = right;
  116.     
  117.     if( largest != index)
  118.     {
  119.         ExchangeSortItem(index, largest);
  120.         Heapify( size, largest);
  121.     }
  122. }
  123.  
  124.